package com.zh.note.leetcode.dp;

import com.zh.note.leetcode.model.TreeNode;

/**
 * 337. 打家劫舍 III
 */
public class LC_337_rob {

    public int rob(TreeNode root) {
        // dp[0]表示不偷，dp[1]表示偷当前节点
        int[] res = dfs(root);
        return Math.max(res[0], res[1]);
    }

    public int[] dfs(TreeNode cur) {
        if (cur == null) {
            return new int[]{0, 0};
        }
        int[] left = dfs(cur.left);
        int[] right = dfs(cur.right);
        // 偷当前节点
        int val1 = cur.val + left[0] + right[0];
        // 不偷当前节点
        int val2 = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        return new int[]{val2, val1};

    }
}
